{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #New 21 Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #sliding-window #probability-and-statistics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #滑动窗口 #概率与统计"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: new21Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #新 21 点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>爱丽丝参与一个大致基于纸牌游戏 <strong>“21点”</strong> 规则的游戏，描述如下：</p>\n",
    "\n",
    "<p>爱丽丝以 <code>0</code> 分开始，并在她的得分少于 <code>k</code> 分时抽取数字。 抽取时，她从 <code>[1, maxPts]</code> 的范围中随机获得一个整数作为分数进行累计，其中 <code>maxPts</code> 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。</p>\n",
    "\n",
    "<p>当爱丽丝获得 <code>k</code> 分 <strong>或更多分</strong> 时，她就停止抽取数字。</p>\n",
    "\n",
    "<p>爱丽丝的分数不超过 <code>n</code> 的概率是多少？</p>\n",
    "\n",
    "<p>与实际答案误差不超过&nbsp;<code>10<sup>-5</sup></code> 的答案将被视为正确答案。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10, k = 1, maxPts = 10\n",
    "<strong>输出：</strong>1.00000\n",
    "<strong>解释：</strong>爱丽丝得到一张牌，然后停止。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, k = 1, maxPts = 10\n",
    "<strong>输出：</strong>0.60000\n",
    "<strong>解释：</strong>爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 21, k = 17, maxPts = 10\n",
    "<strong>输出：</strong>0.73278\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= k &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= maxPts &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [new-21-game](https://leetcode.cn/problems/new-21-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [new-21-game](https://leetcode.cn/problems/new-21-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n1\\n10', '6\\n1\\n10', '21\\n17\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          # 填蓝色的格子\n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        for i in range(K-1,-1,-1):      # 填橘黄色格子\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        # 最长是k+maxPts\n",
    "        dp = [None] * (k + maxPts)\n",
    "        s = 0\n",
    "        for i in range(k, k+maxPts):\n",
    "            dp[i] = 0 if i > n else 1\n",
    "            s += dp[i]\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = 1/maxPts * s\n",
    "            s = s - dp[i+maxPts] + dp[i]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp = [0.0] * (K+W)\n",
    "        #dp[i]表示的是，当前积分为i时，获胜的概率,积分共有K+W种可能\n",
    "        for i in range(K,min(N+1,K+W)):\n",
    "        #想法是，若当前积分大于K，说明不用抽牌了，并且若积分不超过N，游戏结束并且胜利，即获胜概率为1，那么range（K,N+1）里的dp[i]=1.0，但是N+1有可能大于K+W，但实际上达不到那个分数，所以取了更小者。\n",
    "            dp[i]=1.0\n",
    "        #若i大于该范围的右界，则不可能赢，或无法达到那个分数，获胜概率为0，上面已经初始化\n",
    "        S=min(N+1-K,W)\n",
    "        for i in range(K-1,-1,-1):\n",
    "            dp[i] = S/float(W)\n",
    "            S+=dp[i]-dp[i+W]\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp = [0.0] * (K+W)\n",
    "        #dp表示的是，当前积分为i时，获胜的概率\n",
    "        for i in range(K,min(N+1,K+W)):\n",
    "            dp[i]=1.0\n",
    "        #若i大于该范围的右界，则不可能赢，或无法达到那个分数，获胜概率为0，上面已经初始化\n",
    "        #当前积分大于K，说明不用抽牌了，并且此时积分不超过N，游戏结束并且胜利，即获胜概率为1\n",
    "        S=min(N+1-K,W)\n",
    "        #将S初始化为，所有为1的概率之和\n",
    "        for i in range(K-1,-1,-1):\n",
    "            dp[i] = S/float(W)\n",
    "            S+=dp[i]-dp[i+W]\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0]*(k+maxPts)\n",
    "        for i in range(k,k+maxPts):\n",
    "            dp[i] = int(i<=n)\n",
    "        s = sum(dp[k:])\n",
    "        for i in range(k-1,-1,-1):\n",
    "            dp[i] = s/maxPts\n",
    "            s = s-dp[i+maxPts]+dp[i]\n",
    "        return dp[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k == 0 or n >= k + maxPts:\n",
    "            return 1\n",
    "        dp = [0.0] * (k + maxPts)\n",
    "        for i in range(k, n + 1):\n",
    "            dp[i] = 1\n",
    "        res = n + 1 - k\n",
    "        for j in range(k - 1, -1, -1):\n",
    "            dp[j] = res / maxPts\n",
    "            res += dp[j] - dp[j + maxPts]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        \"\"\"ans = 0\n",
    "\n",
    "        def dfs(i,j):\n",
    "            nonlocal ans\n",
    "            if i <= 0:\n",
    "                if i >= k - n:\n",
    "                    ans += (1/maxPts)**j\n",
    "            else:\n",
    "                for p in range(1,maxPts+1):\n",
    "                    dfs(i-p,j+1)\n",
    "        dfs(k,0)\n",
    "        return ans \"\"\"\n",
    "\n",
    "        \"\"\" \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            \n",
    "            if i <= 0:\n",
    "                if i >= k - n:\n",
    "                    \n",
    "                    return ((1/maxPts)**j)\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                tmp = 0\n",
    "                for p in range(1,maxPts+1):\n",
    "                    tmp += dfs(i-p,j+1)\n",
    "                return tmp\n",
    "        return dfs(k,0) \"\"\"\n",
    "    \n",
    "\n",
    "        \"\"\" @cache\n",
    "        def dfs(i):\n",
    "            if i <= 0:\n",
    "                if i >= k-n:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                tmp = 0\n",
    "                for p in range(1,maxPts+1):\n",
    "                    tmp += 1/maxPts * dfs(i-p)\n",
    "                return tmp\n",
    "        return dfs(k) \"\"\"\n",
    "    \n",
    "        #dp\n",
    "        \"\"\" f = [0]*(k+maxPts)\n",
    "        for i in range(k-n+maxPts-1,maxPts):\n",
    "            f[i] = 1\n",
    "        i = maxPts\n",
    "        for j in range(1,maxPts+1):\n",
    "            f[i] += 1/maxPts*f[i-j]    \n",
    "        for i in range(maxPts+1,k+maxPts):\n",
    "\n",
    "            f[i] = f[i-1]-f[i-maxPts-1]/maxPts+f[i-1]/maxPts\n",
    "\n",
    "            \n",
    "        return f[k+maxPts-1] \"\"\"\n",
    "    \n",
    "        #if  k-1 + maxPts <= n:\n",
    "            #return 1\n",
    "\n",
    "\n",
    "        f = [0]*(k+maxPts)\n",
    "        for t in range(maxPts):\n",
    "            if t >= k-n+maxPts-1:\n",
    "                f[t] = 1\n",
    "        for i in range(maxPts,k+maxPts):\n",
    "            if i == maxPts:\n",
    "                for j in range(1,maxPts+1):\n",
    "                    f[i] += 1/maxPts*f[i-j] \n",
    "            else:\n",
    "                f[i] = f[i-1]-f[i-maxPts-1]/maxPts+f[i-1]/maxPts\n",
    "\n",
    "        return f[k+maxPts-1]\n",
    "\n",
    "\n",
    "    \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0.0] * (k + maxPts)\n",
    "        s = 0\n",
    "        for i in range(k, k + maxPts):\n",
    "            dp[i] = 1.0 if i <= n else 0\n",
    "            s += dp[i]\n",
    "        for i in range(k - 1, -1, -1):\n",
    "            dp[i] = s / maxPts\n",
    "            s -= dp[i + maxPts] - dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k==0:\n",
    "            return 1\n",
    "        dp = [0]*(n+1)\n",
    "        rs = 0\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1]\n",
    "            # print(i,dp[i])\n",
    "            \n",
    "            if i>maxPts:\n",
    "                dp[i] -= dp[i-maxPts-1]/maxPts\n",
    "            if i<=k:\n",
    "                dp[i] += dp[i-1]/maxPts\n",
    "            if i==1:\n",
    "                dp[i] += 1/maxPts\n",
    "            if i==maxPts+1:\n",
    "                dp[i] -= 1/maxPts\n",
    "            # for j in range(max(i-maxPts,0),min(i,k)):\n",
    "            #     dp[i] += dp[j]/maxPts\n",
    "            # if i>=1 and i<=maxPts:\n",
    "            #     dp[i] += 1/maxPts\n",
    "            dp[i] = max(dp[i],0)\n",
    "            if i>=k:\n",
    "                rs+=dp[i]\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k - 1 + maxPts <= n or k == 0:\n",
    "            return 1\n",
    "        q, s, ans = deque([1]), 1, 0\n",
    "        for i in range(1, n + 1):\n",
    "            if len(q) > maxPts:\n",
    "                s -= q.popleft()\n",
    "            t = s / maxPts\n",
    "            q.append(t)\n",
    "            if i < k:\n",
    "                s += t\n",
    "            else:\n",
    "                ans += t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0] * (k + maxPts)\n",
    "        s = 0\n",
    "        for i in range(k, k + maxPts):\n",
    "            dp[i] = 1 if i <= n else 0\n",
    "            s += dp[i]\n",
    "\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = s/maxPts\n",
    "            s = s-dp[i+maxPts] + dp[i]\n",
    "        return dp[0]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp = [0.0] * (K+W)\n",
    "        #dp[i]表示的是，当前积分为i时，获胜的概率,积分共有K+W种可能\n",
    "        for i in range(K,min(N+1,K+W)):\n",
    "            dp[i]=1.0\n",
    "        #若i大于该范围的右界，则不可能赢，或无法达到那个分数，获胜概率为0，上面已经初始化\n",
    "        #当前积分大于K，说明不用抽牌了，并且此时积分不超过N，游戏结束并且胜利，即获胜概率为1\n",
    "        S=min(N+1-K,W)\n",
    "        #将S初始化为，所有为1的概率之和\n",
    "        for i in range(K-1,-1,-1):\n",
    "            dp[i] = S/float(W)\n",
    "            S+=dp[i]-dp[i+W]\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0.0] * (k + maxPts)\n",
    "        res = 0\n",
    "        for i in range(k, k + maxPts):\n",
    "            dp[i] = 1 if i <= n else 0\n",
    "            res += dp[i]\n",
    "        for j in range(k - 1, -1, -1):\n",
    "            dp[j] = res / maxPts\n",
    "            res = res + dp[j] - dp[j + maxPts]\n",
    "        return dp[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k==0:\n",
    "            return 1\n",
    "        dp=[0]*(k+maxPts)\n",
    "        for i in range(k,min(n+1,k+maxPts)):\n",
    "            dp[i]=1\n",
    "        dp[k-1]=min(n-k+1,maxPts)/maxPts\n",
    "        for i in range(k-2,-1,-1):\n",
    "            dp[i]+=dp[i+1]-(dp[i+maxPts+1]-dp[i+1])/maxPts\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0]*(k+maxPts)\n",
    "        for i in range(k,k+maxPts):\n",
    "            dp[i] = int(i<=n)\n",
    "        s = sum(dp[k:])\n",
    "        for i in range(k-1,-1,-1):\n",
    "            dp[i] = s/maxPts\n",
    "            s = s-dp[i+maxPts]+dp[i]\n",
    "        return dp[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k-1 + maxPts <= n:\n",
    "            return 1.\n",
    "        \n",
    "        # if n == k\n",
    "        g = [0] * (n+1)\n",
    "        g[0] = 1\n",
    "        s, i = 1, 0\n",
    "        for j in range(1, n+1):\n",
    "            if j - i > maxPts:\n",
    "                s -= g[i]\n",
    "                i += 1\n",
    "            g[j] = s / maxPts\n",
    "            s += g[j]\n",
    "        \n",
    "        p = 1\n",
    "        for i in range(max(0, n-maxPts), k):\n",
    "            p = p - (1 - (n-i)/maxPts) * g[i]\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          \n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        for i in range(K-1,-1,-1):   \n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0] * (k + maxPts + 1)\n",
    "        # dp[i] = dp[i + 1] - (dp[i] - dp[i + maxPts + 1]) / maxPts\n",
    "        for i in range(k, min(n, k + maxPts - 1) + 1):\n",
    "            dp[i] = 1\n",
    "        dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            dp[i] = dp[i + 1] + (dp[i + 1] - dp[i + maxPts + 1]) / maxPts\n",
    "        return dp[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp,s=[1],1\n",
    "        for i in range(1,K+W):\n",
    "            dp.append(s/W)\n",
    "            if i+1>W:s-=dp.pop(0)\n",
    "            if i+1<=K:s+=dp[-1]\n",
    "        return 1 if K==0 else sum(dp[:N-K+1]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp = [0.0] * (K+W)\n",
    "        #dp表示的是，当前积分为i时，获胜的概率\n",
    "        for i in range(K,min(N+1,K+W)):\n",
    "            dp[i]=1.0\n",
    "        #若i大于该范围的右界，则不可能赢，或无法达到那个分数，获胜概率为0，上面已经初始化\n",
    "        #当前积分大于K，说明不用抽牌了，并且此时积分不超过N，游戏结束并且胜利，即获胜概率为1\n",
    "        S=min(N+1-K,W)\n",
    "        #将S初始化为，所有为1的概率之和\n",
    "        for i in range(K-1,-1,-1):\n",
    "            dp[i] = S/float(W)\n",
    "            S+=dp[i]-dp[i+W]\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        d = [0] * (n+maxPts+1)\n",
    "        # d[0] = 1\n",
    "        for i in range(1,maxPts+1):\n",
    "            d[i] = 1/maxPts\n",
    "        s = 0.0\n",
    "        for i in range(k,min(n+1,k+maxPts)):\n",
    "            d[i] = 1.0\n",
    "            s += d[i]\n",
    "        for i in range(k-1,-1,-1):\n",
    "            d[i] = s/maxPts\n",
    "            s = s-d[i+maxPts]+d[i]\n",
    "        # print(d)\n",
    "        return d[0]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0]*(maxPts + k)\n",
    "        s = 0\n",
    "        for i in range(k,maxPts+k):\n",
    "            if i <= n:\n",
    "                dp [i] = 1\n",
    "            s += dp[i]\n",
    "        for i in range(k-1,-1,-1):\n",
    "            dp[i] = s/maxPts\n",
    "            s = s - dp[i+maxPts] + dp[i]\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "        if k == 0 or n >= k + maxPts:\n",
    "            return 1.0\n",
    "        dp = [0.0] * (n + 1)\n",
    "        dp[0] = 1.0\n",
    "        Wsum = 1.0\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = Wsum / maxPts\n",
    "            if i < k:\n",
    "                Wsum += dp[i]\n",
    "            if i - maxPts >= 0:\n",
    "                Wsum -= dp[i - maxPts]\n",
    "        return sum(dp[k:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        # 从0分开始；小于k分从 [1, maxPts]抽取，大于等于k就会停止\n",
    "        # 均匀分布的概率，问累加分数在[k, n]之间的概率，可以拆成两个问题\n",
    "        # 问：爱丽丝的分数不超过 n 的概率是多少？  0 <= k <= n <= 10^4\n",
    "        dp = [0] * (k+maxPts)\n",
    "        s = 0\n",
    "        for i in range(k, k+maxPts):\n",
    "            dp[i] = 1 if i <= n else 0\n",
    "            s += dp[i]\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = s / maxPts\n",
    "            s += dp[i] - dp[i+maxPts]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [None] * (k + maxPts)\n",
    "        s = 0\n",
    "        for i in range(k,k + maxPts):\n",
    "            dp[i] = 1 if i <= n else 0\n",
    "            s += dp[i]\n",
    "        for i in range(k - 1,-1,-1):\n",
    "            dp[i] = s / maxPts\n",
    "            s = s - dp[i + maxPts] + dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          # 填蓝色的格子\n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        for i in range(K-1,-1,-1):      # 填橘黄色格子\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        f = [0.0] * (k + maxPts)\n",
    "        for i in range(k, min(n, k + maxPts - 1) + 1):\n",
    "            f[i] = 1.0\n",
    "        f[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            f[i] = f[i + 1] - (f[i + maxPts + 1] - f[i + 1]) / maxPts\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0] * (k + maxPts)\n",
    "        s = 0\n",
    "        for i in range(k, k + maxPts):\n",
    "            dp[i] = 1 if i <= n else 0\n",
    "            s += dp[i]\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = s / maxPts\n",
    "            s = s - dp[i+maxPts] + dp[i]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        f = [0.0] * (k + maxPts)\n",
    "        for i in range(k, min(n, k + maxPts -1) + 1):\n",
    "            f[i] = 1.0\n",
    "        f[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            f[i] = f[i + 1] - (f[i + maxPts + 1] - f[i + 1]) / maxPts\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0 for _ in range(k+maxPts+1)]\n",
    "        for i in range(k+maxPts, k-1, -1):\n",
    "            if i > n:\n",
    "                dp[i] = 0\n",
    "            elif i+1 <= k+maxPts:\n",
    "                dp[i] = 1 + dp[i+1]\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "        \n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = dp[i+1] + (dp[i+1] - dp[min(n-i, maxPts)+i+1])/maxPts\n",
    "        \n",
    "        return dp[0]-dp[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if n == 0 or k == 0:\n",
    "            return 1\n",
    "        cf = [0.0] * (n + 1)\n",
    "        cf[0] = 1\n",
    "        cf[1] = -1\n",
    "        p = 1 / maxPts\n",
    "        # i+1 ... i+maxPts\n",
    "        for i in range(k):\n",
    "            if i:\n",
    "                cf[i] += cf[i-1]\n",
    "            cf[i+1] += cf[i] * p\n",
    "            if i + maxPts + 1 <= n:\n",
    "                cf[i + maxPts + 1] -= cf[i] * p\n",
    "        ans = 0\n",
    "        for i in range(k,n+1):\n",
    "            cf[i] += cf[i-1]\n",
    "            if k <= i <= n:\n",
    "                ans += cf[i]\n",
    "        return ans\n",
    "\n",
    "\n",
    "s = Solution()\n",
    "\n",
    "s.new21Game(21,17,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          # 填蓝色的格子\n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        for i in range(K-1,-1,-1):      # 填橘黄色格子\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        dp = [0.0] * (k + maxPts)\n",
    "        for i in range(k, min(n, k + maxPts - 1) + 1):\n",
    "            dp[i] = 1.0\n",
    "        dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "#         d = [0] * (k+maxPts)\n",
    "#         d[0] = 1\n",
    "\n",
    "#         pre_sum = 0\n",
    "#         if k > 0:\n",
    "#             pre_sum = 1\n",
    "#         for i in range(1, k + maxPts):\n",
    "#             d[i] = pre_sum / maxPts\n",
    "\n",
    "#             if i < k:\n",
    "#                 pre_sum += d[i]\n",
    "#             if i - maxPts >= 0:\n",
    "#                 pre_sum -= d[i - maxPts]\n",
    "#         d[0] = 0\n",
    "#         #print(d)\n",
    "#         #print(sum(d[k:]))\n",
    "#         if sum(d[k:]) == 0:\n",
    "#             return 1\n",
    "#         return sum(d[k:n+1]) / sum(d[k:])\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        dp = [0.0] * (k + maxPts)\n",
    "        for i in range(k, min(n, k + maxPts - 1) + 1):\n",
    "            dp[i] = 1.0\n",
    "        dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        dp = [0.0] * (k + maxPts)\n",
    "        for i in range(k, min(n, k + maxPts - 1) + 1):\n",
    "            dp[i] = 1.0\n",
    "        dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          # 填蓝色的格子\n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        for i in range(K-1,-1,-1):      # 填橘黄色格子\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k==0:\n",
    "            return 1 \n",
    "              \n",
    "        dp = [0] * (k+maxPts)\n",
    "        # dp[x] denote the probability of winning if start from score x \n",
    "        # dp[0] is the answer we want \n",
    "\n",
    "        for i in range(k, min(n, k+maxPts-1)+1):\n",
    "            dp[i] = 1 \n",
    "        \n",
    "        dp[k-1] = float(min(n-k+1, maxPts)) / maxPts\n",
    "\n",
    "        for i in range(k-2, -1, -1):\n",
    "            dp[i] = dp[i+1] - (dp[i+maxPts+1] - dp[i+1]) / maxPts\n",
    "\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          # 填蓝色的格子\n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        for i in range(K-1,-1,-1):      # 填橘黄色格子\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if n>=(k+maxPts-1):\n",
    "            return 1\n",
    "        m=k+maxPts\n",
    "        dp=[1]*(n+1)\n",
    "     \n",
    "        cur=0\n",
    "        for i in range(1,n+1):\n",
    "            if i<=k:\n",
    "                cur+=dp[i-1]\n",
    "            if k+maxPts>=i>maxPts:\n",
    "                cur -=dp[i-1-maxPts]\n",
    "            dp[i]=cur/maxPts\n",
    "       \n",
    "        #print(dp)\n",
    "        return sum(dp[k:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[1 if i<=N else 0 for i in range(K+W)]\n",
    "        s=sum(dp[K:K+W])\n",
    "        for i in range(K-1,-1,-1):\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        f = [0.0] * (k + maxPts)\n",
    "        for i in range(k, min(n, k + maxPts -1) + 1):\n",
    "            f[i] = 1.0\n",
    "        f[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            f[i] = f[i + 1] - (f[i + maxPts + 1] - f[i + 1]) / maxPts\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          # 填蓝色的格子\n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        for i in range(K-1,-1,-1):      # 填橘黄色格子\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        s = 0\n",
    "        dp = [0] * (k + maxPts)\n",
    "        for i in range(k, k + maxPts):\n",
    "            dp[i] = 1 if i <= n else 0\n",
    "            s += dp[i]\n",
    "        \n",
    "        for i in range(k - 1, -1, -1):\n",
    "            dp[i] = s / maxPts\n",
    "            s = s - dp[i + maxPts] + dp[i]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "#         dp = [0.0]*(k+maxPts)\n",
    "\n",
    "#         for i in range(k, n+1):\n",
    "#             dp[i] = 1.0\n",
    "\n",
    "#         s = n-k+1\n",
    "#         for i in range(k-1, -1, -1):\n",
    "#             dp[k] = s/float(maxPts)\n",
    "#             s+=dp[k] - dp[k+maxPts]\n",
    "#         return dp[0]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int,W: int) ->float:\n",
    "        dp =[0.0]*(N+W)\n",
    "        for k in range(K, N + 1):\n",
    "            dp[k] = 1.0\n",
    "\n",
    "        S=min(N-K+1,W)\n",
    "        \n",
    "        for k in range(K - 1,-1,-1):\n",
    "            dp[k] = S /float(W)\n",
    "            S += dp[k] - dp[k + W]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp = [0.0] * (K+W)\n",
    "        #dp表示的是，当前积分为i时，获胜的概率\n",
    "        for i in range(K,min(N+1,K+W)):\n",
    "            dp[i]=1.0\n",
    "        #若i大于该范围的右界，则不可能赢，或无法达到那个分数，获胜概率为0，上面已经初始化\n",
    "        #当前积分大于K，说明不用抽牌了，并且此时积分不超过N，游戏结束并且胜利，即获胜概率为1\n",
    "        S=min(N+1-K,W)\n",
    "        #将S初始化为，所有为1的概率之和\n",
    "        for i in range(K-1,-1,-1):\n",
    "            dp[i] = S/float(W)\n",
    "            S+=dp[i]-dp[i+W]\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        f = [0.0] * (k + maxPts)\n",
    "        for i in range(k, min(n, k + maxPts -1) + 1):\n",
    "            f[i] = 1.0\n",
    "        f[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            f[i] = f[i + 1] - (f[i + maxPts + 1] - f[i + 1]) / maxPts\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0]*(k+maxPts)\n",
    "        i = k+maxPts-1\n",
    "        while i >=0:\n",
    "            if i >=k:\n",
    "                dp[i] = int(i<=n)\n",
    "                i -=1\n",
    "            else:\n",
    "                if i == k-1:\n",
    "                    s = sum(dp[k:])\n",
    "                else:\n",
    "                    s = s-dp[i+maxPts+1]+dp[i+1]\n",
    "                dp[i] = s/maxPts\n",
    "                i -=1\n",
    "        return dp[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0] * (k + maxPts)\n",
    "        s = 0\n",
    "        for i in range(k, k + maxPts):\n",
    "            if i <= n:\n",
    "                dp[i] = 1\n",
    "                s += 1\n",
    "            else:\n",
    "                break\n",
    "        for i in range(k - 1, -1, -1):\n",
    "            dp[i] = s / maxPts\n",
    "            s += dp[i] - dp[i + maxPts]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k==0: return 1.0 \n",
    "        dp=[0.0]*(k+maxPts)\n",
    "        s=  0\n",
    "        for i in range(k,min(n,k+maxPts-1)+1):\n",
    "            dp[i] = 1.0\n",
    "            s+=dp[i]\n",
    "        for i in range(k-1,-1,-1):\n",
    "            dp[i] = s/maxPts\n",
    "            s = s-dp[i+maxPts]+dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          # 填蓝色的格子\n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        for i in range(K-1,-1,-1):      # 填橘黄色格子\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k == 0 or n >= k + maxPts:\n",
    "            return 1\n",
    "        \n",
    "        dp = [0.0] * (n + 1)\n",
    "        dp[0] = 1.0\n",
    "\n",
    "        W = 1.0\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = W / maxPts\n",
    "\n",
    "            if i < k:\n",
    "                W += dp[i]\n",
    "            \n",
    "            if i - maxPts >= 0:\n",
    "                W -= dp[i - maxPts]\n",
    "        return sum(dp[k:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [None] * (k + maxPts)\n",
    "        s = 0\n",
    "        for i in range(k, k + maxPts):\n",
    "            dp[i] = 1 if i <= n else 0\n",
    "            s += dp[i]\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = s / maxPts\n",
    "            s = s - dp[i + maxPts] + dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\r\n",
    "        dp=[0]*(k+maxPts)\r\n",
    "        bound=min(n,k+maxPts-1)\r\n",
    "        for i in range(k,bound+1):\r\n",
    "            dp[i]=1\r\n",
    "        dp[k-1]=(bound-k+1)/maxPts\r\n",
    "        for i in range(k-2,-1,-1):\r\n",
    "            # dp[i]=dp[i+1]-(dp[i+1]-dp[i+1+maxPts])/maxPts\r\n",
    "            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts\r\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0.0] * (k+maxPts)\n",
    "        for i in range(k,min(n+1,k+maxPts)):\n",
    "            dp[i] = 1.0 \n",
    "        # for i in range(k-1,-1,-1):# 从后先前\n",
    "        #     tmp = 0 \n",
    "        #     for j in range(maxPts):\n",
    "        #         tmp += dp[i +j + 1]\n",
    "        #     dp[i] = tmp/float(maxPts)\n",
    "\n",
    "        s = min(n-k + 1 ,maxPts)\n",
    "        for i in range(k-1,-1,-1):\n",
    "            dp[i] = s /float(maxPts)\n",
    "            s += dp[i] - dp[i+maxPts]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0.0] * (k + maxPts)\n",
    "        value = 0\n",
    "        for i in range(k, min(k+maxPts, n+1)) :\n",
    "            dp[i] = 1\n",
    "            value += dp[i]\n",
    "        dp[k-1] = value / maxPts\n",
    "        for i in range(k-2, -1, -1) :\n",
    "            value -= dp[i+maxPts+1]\n",
    "            value += dp[i+1]\n",
    "            dp[i] = value/maxPts\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0 for i in range(k+maxPts)]\n",
    "        for m in range(k, k+maxPts, 1):\n",
    "            dp[m] = 1 if m <= n else 0\n",
    "        moving_sum = sum(dp[k:k+maxPts])  \n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = moving_sum / maxPts\n",
    "            moving_sum -= dp[i+maxPts]\n",
    "            moving_sum += dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0] * (k + maxPts)\n",
    "        s = 0\n",
    "        for i in range(k, k + maxPts):\n",
    "            dp[i] = 1 if i <= n else 0\n",
    "            s += dp[i]\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = s / maxPts\n",
    "            s = s - dp[i+maxPts] + dp[i]\n",
    "        return dp[0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, w: int) -> float:\n",
    "        f = [0] * 20010\n",
    "        for i in range(k, n + 1):\n",
    "            f[i] = 1\n",
    "        for i in range(1, w + 1):\n",
    "            f[k - 1] += f[i + k - 1] / w\n",
    "        for i in range(k - 2, -1, -1):\n",
    "            f[i] = f[i + 1] + (f[i + 1] - f[i + w + 1]) / w\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #DFS, ETL\n",
    "    # def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "    #     @cache\n",
    "    #     def dfs(score):\n",
    "    #         if score >= k:\n",
    "    #             return 1 if score <= n else 0\n",
    "    #         res = 0\n",
    "    #         for i in range(1, maxPts+1):\n",
    "    #             if score + i > n:\n",
    "    #                 return res\n",
    "    #             res += dfs(score+i) / maxPts\n",
    "    #         return res\n",
    "    #     return dfs(0)\n",
    "\n",
    "    #DP + optimization\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0] * (k + maxPts)\n",
    "        for i in range(k, min(n+1, k + maxPts)):\n",
    "            dp[i] = 1\n",
    "        cnt = sum(dp[k:])\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = cnt / maxPts\n",
    "            cnt += dp[i]\n",
    "            cnt -= dp[i+maxPts]\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        presum = [0] * (k + maxPts)\n",
    "        presum[0] = 1\n",
    "        for i in range(1, k+maxPts):\n",
    "            r = min(i-1, k-1)\n",
    "            l = max(i-maxPts-1,-1)\n",
    "            presum[i] = (presum[r] - presum[l])/maxPts + presum[i-1]\n",
    "            # presum[i] = dp[i] + presum[i-1]\n",
    "            # for j in range(min(i-1, k-1), max(i-maxPts-1,-1), -1):\n",
    "            #     dp[i] += dp[j]/maxPts\n",
    "        # print(sum(dp))\n",
    "        # print(dp)\n",
    "        return presum[min(n+1, k + maxPts)-1] - presum[k-1]\n",
    "        # return sum(dp[k:min(n+1, k + maxPts)])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[1 if i<=N else 0 for i in range(K+W)]\n",
    "        s=sum(dp[K:K+W])\n",
    "        for i in range(K-1,-1,-1):\n",
    "            dp[i]=s/W\n",
    "            s -= dp[i+W] - dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [1 if i <= n else 0 for i in range(k+maxPts)]\n",
    "        s = sum(dp[k:k+maxPts])\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = s/maxPts\n",
    "            s = s-dp[i+maxPts] + dp[i]\n",
    "        return dp[0]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "        d = [0] * (k+maxPts)\n",
    "        d[0] = 1\n",
    "\n",
    "        pre_sum = 0\n",
    "        if k > 0:\n",
    "            pre_sum = 1\n",
    "        for i in range(1, k + maxPts):\n",
    "            d[i] = pre_sum / maxPts\n",
    "\n",
    "            if i < k:\n",
    "                pre_sum += d[i]\n",
    "            if i - maxPts >= 0:\n",
    "                pre_sum -= d[i - maxPts]\n",
    "        d[0] = 0\n",
    "        #print(d)\n",
    "        #print(sum(d[k:]))\n",
    "        if (s := sum(d[k:])) == 0:\n",
    "            return 1\n",
    "        return sum(d[k:n+1]) / s\n",
    "\n",
    "# from ans, faster about 50% than mines\n",
    "# random run performance\n",
    "# class Solution:\n",
    "#     def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "#         if k == 0:\n",
    "#             return 1.0\n",
    "#         dp = [0.0] * (k + maxPts)\n",
    "#         for i in range(k, min(n, k + maxPts - 1) + 1):\n",
    "#             dp[i] = 1.0\n",
    "#         dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "#         for i in range(k - 2, -1, -1):\n",
    "#             dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts\n",
    "#         return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, N: int, K: int, W: int) -> float:\n",
    "        dp=[None]*(K+W)\n",
    "        s=0\n",
    "        for i in range(K,K+W):          # 填蓝色的格子\n",
    "            dp[i] = 1 if i<=N else 0\n",
    "            s+=dp[i]\n",
    "        print(dp)\n",
    "        for i in range(K-1,-1,-1):      # 填橘黄色格子\n",
    "            dp[i]=s/W\n",
    "            s=s-dp[i+W]+dp[i]\n",
    "        return dp[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n, k, maxPts):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :type maxPts: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        info = [-1 for i in range(k+maxPts)]\n",
    "        s  = 0\n",
    "        for i in range(k,k+maxPts):\n",
    "            info[i] = float(i<=n)\n",
    "            s += info[i]\n",
    "        for i in range(k-1,-1,-1):\n",
    "            info[i] = s/maxPts\n",
    "            s = s - info[i+maxPts] + info[i]\n",
    "        return info[0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0] * (n+1)\n",
    "        pre = [0] * (n+1) \n",
    "        dp[0] = 1\n",
    "        pre[0] = 0\n",
    "        if n == 0 or k == 0:\n",
    "            return 1 \n",
    "        if n >= k + maxPts - 1:\n",
    "            return 1 \n",
    "        for i in range(1, n+1):\n",
    "            if i <= k:\n",
    "                a, b, c = pre[i-1], pre[i-min(i,maxPts)], dp[i-min(i,maxPts)]\n",
    "            else:\n",
    "                a, b, c = pre[k-1], pre[i-min(i,maxPts)], dp[i-min(i,maxPts)]\n",
    "            dp[i] = (a - b + c) / maxPts \n",
    "            pre[i] = pre[i-1] + dp[i]\n",
    "        \n",
    "        return pre[n] - pre[k-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        # 使用动态规划,不同的投掷次数，概率是不同的\n",
    "        if k == 0:\n",
    "            return 1.0\n",
    "        p = 1 / maxPts\n",
    "        dp1 = [p for i in range(maxPts + 1)]\n",
    "        dp2 = [0] * k\n",
    "        dp = dp1 + dp2\n",
    "        dp[0] = 0\n",
    "        # print(\"test\",dp)\n",
    "        for i in range(2,k + maxPts + 1):\n",
    "            l = max(1,i-maxPts)\n",
    "            r = min(k,i)\n",
    "            # print(i,l,r,sum(dp[l:r]),dp[i],)\n",
    "            dp[i] += sum(dp[l:r]) * p\n",
    "            \n",
    "        # print(dp)\n",
    "        a = sum(dp[k:n + 1])\n",
    "        b = sum(dp[k:])\n",
    "        # print(a,b)\n",
    "        return a / b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        sm = [0.0] * (n + 1)\n",
    "        dp = [0.0] * (n + 1)\n",
    "        dp[0] = 1.0\n",
    "        for i in range(1, n + 1):\n",
    "            sm[i] = dp[i - 1] + sm[i - 1]\n",
    "            l, r = max(0, i - maxPts), min(i, k)\n",
    "            if r > l:\n",
    "                dp[i] = (sm[r] - sm[l]) / maxPts\n",
    "        return sm[n] - sm[k] + dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if n == 0 or k == 0:\n",
    "            return 1\n",
    "        dp = [0.0] * (n + 1)\n",
    "        cf = [0.0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        p = 1 / maxPts\n",
    "        # i+1 ... i+maxPts\n",
    "        for i in range(k):\n",
    "            if i:\n",
    "                cf[i] += cf[i-1]\n",
    "            dp[i] += cf[i]\n",
    "            cf[i+1] += dp[i] * p\n",
    "            if i + maxPts + 1 <= n:\n",
    "                cf[i + maxPts + 1] -= dp[i] * p\n",
    "        ans = 0\n",
    "        for i in range(k,n+1):\n",
    "            cf[i] += cf[i-1]\n",
    "            if k <= i <= n:\n",
    "                ans += cf[i]\n",
    "        return ans\n",
    "\n",
    "\n",
    "s = Solution()\n",
    "\n",
    "s.new21Game(21,17,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        p = [0] * (n + 1)\n",
    "        sump = [0] * (n + 2)\n",
    "        p[0] = 1\n",
    "        sump[1] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            l, r = max(0, i - maxPts), min(k - 1, i - 1)\n",
    "            if l <= r:\n",
    "                p[i] = (sump[r + 1] - sump[l]) / maxPts\n",
    "            sump[i + 1] = sump[i] + p[i]\n",
    "        return sump[n + 1] - sump[k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if k==0:\n",
    "            return 1\n",
    "        dp = [0]*(n+1)\n",
    "        rs = 0\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1]\n",
    "            # print(i,dp[i])\n",
    "            \n",
    "            if i>maxPts:\n",
    "                dp[i] -= dp[i-maxPts-1]/maxPts\n",
    "            if i<=k:\n",
    "                dp[i] += dp[i-1]/maxPts\n",
    "            if i==1:\n",
    "                dp[i] += 1/maxPts\n",
    "            if i==maxPts+1:\n",
    "                dp[i] -= 1/maxPts\n",
    "            # for j in range(max(i-maxPts,0),min(i,k)):\n",
    "            #     dp[i] += dp[j]/maxPts\n",
    "            # if i>=1 and i<=maxPts:\n",
    "            #     dp[i] += 1/maxPts\n",
    "            dp[i] = max(dp[i],0)\n",
    "            if i>=k:\n",
    "                rs+=dp[i]\n",
    "        print(dp)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        dp = [0] * (k + maxPts)\n",
    "        for i in range(k, n+1):\n",
    "            if i > k - 1 + maxPts:\n",
    "                break\n",
    "            dp[i] = 1\n",
    "        sufsum = [0] * (k + maxPts + 1)\n",
    "        for i in range(k - 1 + maxPts, k-1, -1):\n",
    "            sufsum[i] = sufsum[i+1] + dp[i]\n",
    "        for i in range(k-1, -1, -1):\n",
    "            dp[i] = (sufsum[i+1] - sufsum[i+1+maxPts])/ maxPts\n",
    "            sufsum[i] = sufsum[i+1] + dp[i]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "        d = [0] * (k+maxPts)\n",
    "        d[0] = 1\n",
    "\n",
    "        pre_sum = 0\n",
    "        if k > 0:\n",
    "            pre_sum = 1\n",
    "        for i in range(1, k + maxPts):\n",
    "            d[i] = pre_sum / maxPts\n",
    "\n",
    "            if i < k:\n",
    "                pre_sum += d[i]\n",
    "            if i - maxPts >= 0:\n",
    "                pre_sum -= d[i - maxPts]\n",
    "        d[0] = 0\n",
    "        #print(d)\n",
    "        #print(sum(d[k:]))\n",
    "        if (s := sum(d[k:])) == 0:\n",
    "            return 1\n",
    "        return sum(d[k:n+1]) / s\n",
    "\n",
    "# from ans, faster about 50% than mines\n",
    "# class Solution:\n",
    "#     def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "#         if k == 0:\n",
    "#             return 1.0\n",
    "#         dp = [0.0] * (k + maxPts)\n",
    "#         for i in range(k, min(n, k + maxPts - 1) + 1):\n",
    "#             dp[i] = 1.0\n",
    "#         dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts\n",
    "#         for i in range(k - 2, -1, -1):\n",
    "#             dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts\n",
    "#         return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "\n",
    "        d = [0] * (k+maxPts)\n",
    "        d[0] = 1\n",
    "\n",
    "        pre_sum = 0\n",
    "        if k > 0:\n",
    "            pre_sum = 1\n",
    "        for i in range(1, k + maxPts):\n",
    "            d[i] = pre_sum / maxPts\n",
    "\n",
    "            if i < k:\n",
    "                pre_sum += d[i]\n",
    "            if i - maxPts >= 0:\n",
    "                pre_sum -= d[i - maxPts]\n",
    "        d[0] = 0\n",
    "        #print(d)\n",
    "        #print(sum(d[k:]))\n",
    "        if sum(d[k:]) == 0:\n",
    "            return 1\n",
    "        return sum(d[k:n+1]) / sum(d[k:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n",
    "        if n>=(k+maxPts-1):\n",
    "            return 1\n",
    "        m=k+maxPts\n",
    "        dp=[1]*(n+1)\n",
    "     \n",
    "        cur=0\n",
    "        for i in range(1,n+1):\n",
    "            if i<=k:\n",
    "                cur+=dp[i-1]\n",
    "            if k+maxPts>=i>maxPts:\n",
    "                cur -=dp[i-1-maxPts]\n",
    "            dp[i]=cur/maxPts\n",
    "       \n",
    "        print(dp)\n",
    "        return sum(dp[k:])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
